#pragma once

#include <iostream>
using namespace std;

#include "BinaryTreeBase.h"

//双链表实现队列
typedef struct TreeNodeQueue{
	BinaryTreeNode* data;
	TreeNodeQueue* pre;
	TreeNodeQueue* next;
}TreeNodeQueue;

//初始化
TreeNodeQueue* InitTreeNodeQueue(){
	TreeNodeQueue* q = (TreeNodeQueue*)malloc(sizeof(TreeNodeQueue));
	q->data = nullptr;
	q->pre = q;
	q->next = q;

	return q;
}

//插入元素
// q 作为队列头节点
// n2 <- q <->  n1 <-> n2 -> q
void EnQueue(BinaryTreeNode *node, TreeNodeQueue *q) {
	TreeNodeQueue* qNode = (TreeNodeQueue*)malloc(sizeof(TreeNodeQueue));
	qNode->data = node;
	qNode->next = q;
	qNode->pre = q->pre;

	q->pre->next = qNode;
	q->pre = qNode;
}

//是否为空
bool IsEmpty(TreeNodeQueue *q) {
	if (q->next == q) {
		return true;
	}
	return false;
}

//取出元素
TreeNodeQueue* Dequeue(TreeNodeQueue* q) {
	if (IsEmpty(q)) {
		return nullptr;
	}
	else {
		TreeNodeQueue *dequeueNode = q->next;
		q->next = dequeueNode->next;
		dequeueNode->next->pre = q;
		dequeueNode->next = nullptr;
		dequeueNode->pre = nullptr;
		return dequeueNode;
	}
}


//树的层序遍历, 使用队列(双向链表)实现
void LevelTravelBinaryTree(BinaryTreeNode *T) {
	TreeNodeQueue* q = InitTreeNodeQueue();
	EnQueue(T, q);

	while (!IsEmpty(q)){
		TreeNodeQueue* qNode = Dequeue(q);
		cout << qNode->data->data << " ";
		if (qNode->data->LChild != nullptr) {
			EnQueue(qNode->data->LChild, q);
		}
		if (qNode->data->RChild != nullptr) {
			EnQueue(qNode->data->RChild, q);
		}
	}

	delete q;
}